Algoritmo Euclideo Esteso

L'Algoritmo Euclideo Esteso è un'estensione dell'Algoritmo Euclideo che non solo calcola il massimo comune divisore (MCD) di due interi \(A\) e \(B\), ma trova anche i coefficienti dell'identità di Bézout, che sono gli interi \(x\) e \(y\) tali che \(Ax + By = \text{MCD}(A, B)\).

Descrizione dell'Algoritmo

L'Algoritmo Euclideo Esteso può essere descritto utilizzando i seguenti passaggi:

1. Inizia con due numeri interi positivi \(A\) e \(B\), dove \(A \geq B\).
2. Esegui i passaggi dell'Algoritmo Euclideo per trovare il MCD di \(A\) e \(B\).
3. Contemporaneamente, calcola i coefficienti \(x\) e \(y\) tali che \(Ax + By = \text{MCD}(A, B)\).
4. Aggiorna \(x\) e \(y\) utilizzando le relazioni ricorsive derivate dai passaggi dell'Algoritmo Euclideo.

Rappresentazione Matematica

L'Algoritmo Euclideo Esteso può essere rappresentato matematicamente come:

\[ \begin{aligned} &\text{Dato } A \text{ e } B, \text{ con } A \geq B: \\ &\text{1. Se } B = 0, \text{ allora } \text{MCD}(A, B) = A \text{ e } x = 1, y = 0. \\ &\text{2. Altrimenti, eseguire l'Algoritmo Euclideo:} \\ &\hspace{20px} A = BQ + R \text{, dove } R = A \mod B \\ &\hspace{20px} \text{MCD}(A, B) = \text{MCD}(B, R) \\ &\hspace{20px} \text{Trova ricorsivamente i coefficienti } x_1 \text{ e } y_1 \text{ tali che } Bx_1 + Ry_1 = \text{MCD}(B, R) \\ &\hspace{20px} \text{Imposta } x = y_1 \text{ e } y = x_1 - Qy_1 \\ &\text{3. Restituisci } \text{MCD}(A, B), x \text{ e } y. \end{aligned} \]

Esempio

Troviamo il MCD e i coefficienti di Bézout di \(A = 252\) e \(B = 105\) utilizzando l'Algoritmo Euclideo Esteso:

1. Inizia con \(A = 252\) e \(B = 105\).
2. Calcola \(252 \mod 105 = 42\). \(252 = 105 \times 2 + 42\).
3. Calcola \(105 \mod 42 = 21\). \(105 = 42 \times 2 + 21\).
4. Calcola \(42 \mod 21 = 0\). \(42 = 21 \times 2 + 0\).
5. Sostituisci all'indietro per trovare \(x\) e \(y\):
   \(21 = 105 - 42 \times 2\)
   \(42 = 252 - 105 \times 2\)
   Quindi, \(21 = 105 - 2(252 - 105 \times 2) = 105 \times 5 - 252 \times 2\).
   Così, \(x = -2\) e \(y = 5\).

Pertanto, il MCD di 252 e 105 è 21, con i coefficienti di Bézout \(x = -2\) e \(y = 5\), tali che \(252(-2) + 105(5) = 21\).

---

Comprendere l'Algoritmo Euclideo Esteso

L'Algoritmo Euclideo Esteso utilizza le seguenti proprietà chiave:

• Estende l'Algoritmo Euclideo tracciando i coefficienti \(x\) e \(y\) nell'identità di Bézout.
• L'algoritmo mantiene la relazione \(Ax + By = \text{MCD}(A, B)\) durante tutti i suoi passaggi.
• Permette il calcolo degli inversi modulari, fondamentali in molti algoritmi crittografici, incluso RSA.

Dimostrazioni

Possiamo dimostrare la correttezza dell'algoritmo attraverso dimostrazioni:

• Prova dell'Identità di Bézout: Per interi \(A\) e \(B\), con MCD \(d\), esistono interi \(x\) e \(y\) tali che \(Ax + By = d\). Questo è mostrato dal processo iterativo di sostituzione all'indietro dai passaggi dell'Algoritmo Euclideo. \(\square\)


• Prova che l'Algoritmo Produce Coefficienti Correttamente:
  
  

  Per induzione sui passaggi dell'Algoritmo Euclideo:

  
  

  1. Caso Base: Se \(B = 0\), allora \(d = A\), e i coefficienti sono \(x = 1\) e \(y = 0\), che soddisfano \(Ax + By = d\).

  
  

  2. Passo Induttivo: Supponiamo per \(B\) e \(R = A \mod B\), abbiamo \(Bx_1 + Ry_1 = \text{MCD}(B, R)\). Allora, dall'Algoritmo Euclideo, \(R = A - BQ\), sostituendo, otteniamo:

  
  

  \(\text{MCD}(A, B) = Bx_1 + (A - BQ)y_1 = Ay_1 + B(x_1 - Qy_1)\).

  
  

  Quindi, i nuovi coefficienti \(x = y_1\) e \(y = x_1 - Qy_1\) soddisfano \(Ax + By = \text{MCD}(A, B)\). \(\square\)

Ora che abbiamo dimostrato la validità dell'algoritmo, dobbiamo dimostrare che l'algoritmo termina in un numero finito di passaggi.

• Prova che l'Algoritmo Termina in un Numero Finito di Passaggi:
  
  

  Poiché l'Algoritmo Euclideo Esteso segue gli stessi passaggi dell'Algoritmo Euclideo per trovare il MCD, termina in un numero finito di passaggi come dimostrato per l'Algoritmo Euclideo. \(\square\)

L'Algoritmo Euclideo Esteso è essenziale per risolvere le equazioni diofantee lineari e trovare gli inversi modulari, che sono vitali in applicazioni crittografiche come l'algoritmo di crittografia RSA.